package algotithm.leetcode.dp.hot.test312;

/**
 * @author zhouyanxiang
 * @Date 2021-02-2021/2/11-21:05
 * @URL https://leetcode-cn.com/problems/burst-balloons/
 * @Title 312. 戳气球
 */
public class Solution {

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums = {3,1,5,8};
        int num = solution.maxCoins(nums);
        System.out.println(num);
    }

    public int maxCoins(int[] nums) {
        int n = nums.length;
        int[][] rec = new int[n+2][n+2];
        int[] arr = new int[n+2];
        arr[0] = arr[n+1] = 1;
        for (int i = 1; i <= n; i++) {
            arr[i] = nums[i-1];
        }

        for (int i = n - 1; i >= 0; i--) {
            for (int j = i + 2; j <= n + 1; j++) {
                for (int k = i + 1; k < j; k++) {
                    int sum = arr[i] * arr[k] * arr[j];
                    sum += rec[i][k] + rec[k][j];
                    rec[i][j] = Math.max(rec[i][j],sum);
                }
            }
        }
        return rec[0][n+1];
    }
}
